The Fourier Transform can be used to map a time domain signal to its frequency domain counterpart. Conversely, an Inverse Fourier Transform can be used to map a frequency domain signal to its time domain counterpart. Fourier transforms are particularly useful for spectral analysis of time domain signals. Additionally, communication systems, such as those implementing Orthogonal Frequency Division Multiplexing (OFDM) can use the properties of Fourier transforms to generate multiple time domain symbols from linearly spaced tones and to recover the frequencies from the symbols.
A sampled data system can implement a Discrete Fourier Transform (DFT) to allow a processor to perform the transform on a predetermined number of samples. However, the DFT is computationally intensive and requires a tremendous amount of processing power to perform. The number of computations required to perform an N point DFT is on the order of N2, denoted O(N2). In many systems, the amount of processing power dedicated to performing a DFT may reduce the amount of processing available for other system operations. Additionally, systems that are configured to operate as real time systems may not have sufficient processing power to perform a DFT of the desired size within a time allocated for the computation.
The Fast Fourier Transform (FFT) is a discrete implementation of the Fourier transform that allows a Fourier transform to be performed in significantly fewer operations compared to the DFT implementation. Depending on the particular implementation, the number of computations required to perform an FFT of radix r is typically on the order of N×logr(N), denoted as O(Nlogr(N)).
In the past, systems implementing an FFT may have used a general purpose processor or stand alone Digital Signal Processor (DSP) to perform the FFT. However, systems are increasingly incorporating Application Specific Integrated Circuits (ASIC) specifically designed to implement the majority of the functionality required of a device. Implementing system functionality within an ASIC minimizes the chip count and glue logic required to interface multiple integrated circuits. The reduced chip count typically allows for a smaller physical footprint for devices without sacrificing any of the functionality.
The amount of area within an ASIC die is limited, and functional blocks that are implemented within an ASIC need to be size, speed, and power optimized to improve the functionality of the overall ASIC design. The amount of resources dedicated to the FFT should be minimized to limit the percentage of available resources dedicated to the FFT. Yet sufficient resources need to be dedicated to the FFT to ensure that the transform may be performed with a speed sufficient to support system requirements. Additionally, the amount of power consumed by the FFT module needs to be minimized to minimize the power supply requirements and associated heat dissipation. Therefore, it may be desirable to optimize an FFT architecture for implementation within an integrated circuit, such as an ASIC.